一、今日目標

演算法的核心是效率。
同一個問題，或許有 10 種方法，但只有時間複雜度最優的才適合大規模資料。
然而，暴力法（Brute Force）並不總是壞事，小範圍題目時暴力是最快上手的解法。
今天會學到：

• Big-O 複雜度判斷
• 暴力法的使用時機
• 如何用暴力法快速解決小範圍題目

二、時間複雜度 Big-O 完整解析

常見時間複雜度表

快速判斷技巧：

• n ≤ 10³：O(n²) 或 O(2ⁿ) 還能接受。
• n ≤ 10⁵：盡量使用 O(n log n)。
• n ≥ 10⁶：必須是 O(n) 或 O(1)。

暴力法 (Brute Force)

暴力法就是窮舉所有可能解。
它簡單、好寫，但必須確認輸入規模小才能使用。

適用情況：

• n 很小（例如 n ≤ 10³）
• 題目只求單一結果，不需高效優化
• 沒有更優解，先寫暴力解測試正確性

三、CSES 實戰演練

題目1：Repetitions

原題:
https://cses.fi/problemset/task/1069/
題意：
給定一個 DNA 序列（只包含 A/C/G/T），找出最長連續相同字元長度。

解題思路:

• 遍歷一次字串：
  • 如果當前字元和前一個一樣 → now++
  • 否則重置 now=1
• 持續更新 ans = max(ans, now)

#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	int now=1,ans=0;
	for(int i=1;i<=s.size();i++){
		if(i<s.size() and s[i]==s[i-1]) now++;
		else{
			ans=max(ans,now);
			now=1;
		}
	}
	cout<<ans<<endl;
}

時間複雜度:O(n)，因為只從頭到尾遍歷一次。

題目2：Creating Strings

原題:
https://cses.fi/problemset/task/1622

題意：
給定一個字串，輸出所有不同的排列（Permutation），並且按字典序排序。

解題思路

• 使用 next_permutation 生成所有排列。
• 排序後用 set 去重（或直接用 STL 生成）。

STL：next_permutation

用途：將 [first, last) 區間的元素重新排列成字典序下一個排列。
返回值：

• 如果成功產生下一個排列 → true
• 如果當前是最後一個排列（最大字典序） → 會重新排列為最小字典序，並返回 false

使用步驟:

• 先對字串或容器排序 → 確保從最小字典序開始。
• 在 do { ... } while(next_permutation(...)) 裡面持續生成。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;

    sort(s.begin(), s.end());

    vector<string> result;
    do {
        result.push_back(s);
    } while (next_permutation(s.begin(), s.end()));

    cout << result.size() << "\n";
    for (auto &str : result) cout << str << "\n";

    return 0;
}

時間複雜度:O(n × n!)，因為排列數量為 n!（n ≤ 8，可直接暴力）

四、LeetCode 實戰演練

題目1：Two Sum

原題:
https://leetcode.com/problems/two-sum/description/

題意：
給定一個整數陣列 nums 和一個目標值 target，找出任意兩個數字，使得它們的和等於 target。

解題思路:

1. 暴力法 (O(n²)):兩層迴圈，嘗試所有數字對。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target)
                    return {i, j};
            }
        }
        return {};
    }
};

2. 優化 (O(n)):用 unordered_map 紀錄差值，單次遍歷完成。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> mp;
        for (int i = 0; i < nums.size(); i++) {
            int diff = target - nums[i];
            if (mp.count(diff))
                return {mp[diff], i};
            mp[nums[i]] = i;
        }
        return {};
    }
};

題目2：Subsets

原題:
https://leetcode.com/problems/subsets/description/

題意：
給定一個整數陣列，輸出所有可能的子集合（包含空集合）。

解題思路:
一開始只有空集合：[[]]
每來一個數字，就把現有的每個子集複製一份，並加上這個數字
舉例：nums = [1, 2]
初始：[[]]
加入 1：[[], [1]]
加入 2：[[], [1], [2], [1, 2]]

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res = {{}};

        for (int num : nums) {
            int n = res.size();
            for (int i = 0; i < n; i++) {
                vector<int> subset = res[i]; //複製一份
                subset.push_back(num);  // 加上新元素
                res.push_back(subset);  // 加入結果
            }
        }
        return res;
    }
};